perm filename NOTES.END[LSP,JRA]4 blob sn#098594 filedate 1974-04-24 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00026 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00004 00002	.SEC(Compilation)
C00025 00003	.SS(More on Compilation,compiler)
C00034 00004	.SS(Compilers for subsets of LISP)
C00047 00005	.SS(Problems)
C00048 00006	.SS(One-pass Assemblers,assemblers,P7:)
C00061 00007	.SS(A compiler for simple %3eval%*,compiler,P32:)
C00065 00008	.<<discussion of offset and vpl>>
C00076 00009	Here is a partial sketch of %3compile%* operating on %3j <= λ[[xy]f[g[x]h[y]]].%*
C00080 00010	.SS(A project: Efficient compilation)
C00084 00011	.SS(A project: One-pass assembler)
C00087 00012	.SS(A project: Syntax directed compilation,syntax-directed,P4:)
C00088 00013	.SS(A deep-binding compiler,deep binding)
C00089 00014	.SS(Compilation and global variables,global variables,P5:)
C00097 00015	.SS(Functional Arguments,,P3:)
C00104 00016	.SS(Tracing and debugging in LISP)
C00110 00017	.SS(Macros and special forms,macros,P57:)
C00125 00018	.SS(Numbers,numbers)
C00129 00019	.SEC(Storage structures and efficiency)
C00134 00020	.SS(Bit-tables)
C00136 00021	.SS(Vectors and arrays)
C00143 00022	A typical implementation on an array facility in LISP would include
C00145 00023	.SS(strings and linear LISP,string processor,P27:)
C00155 00024	.SS(%3rplaca%* and %3rplacd%*)
C00160 00025	.SS(Applications of %3rplaca%* and %3rplacd%*)
C00174 00026	.SEC(Systems Organization)
C00196 ENDMK
C⊗;
.SEC(Compilation)
.TURN ON "←";
.SS(On LISP and Semantics)
LISP should be the first language learned by Computer Science majors.
As a mathematical language for studies algorithms for data structures, it is
presently without peer.  As you are seeing now, the problems of language implementation and their solutions are describable
quite easily in the implementation of LISP (symbol tables, hashing, garbage
collection, stacks, linked allocation, lists, etc. etc.)  At the theoretical
level, questions of provability of properties of programs are tractable.  As a
programming language, LISP has exceptionally powerful features possessed by few
languages.  In particular the uniform representation of program and data.  LISP
is also quite useful in understanding the ⊗→semantics↔← of programming languages.  The
study of semantics is motivated by the desire to have a tool for describing
the meaning of constructs of a language; in particular, a tool of the power and
clarity of BNF descriptions of the syntax of languages.

The field of programming language semantics is full of ⊗→bull↔← written by people who don't
understand the problem. Here is some more by another.
There are many different schools of thought concerning appropriate means
for describing semantics.
One thought is to describe the meaning of a language in terms of the process
of compilation.  That is, the semantic is specified by some canonical compiler
producing code of some standard machine-independent machine.  The meaning of
a program is the outcome of an interpreter interpreting this machine-independent
code.

The key problem is:  just what is the semantic specification supposed to
do?  If it is truly to help a programmer (be he implementor or applications)
to understand the meaning of a particular constructs, then this proposal is
lacking.  To understand a construct now requires that you read the description 
of a compiler--a non-trivial task, and understand two machines-- the machine-
independent and the real machine.  There is a more fundamental difficulty here.
When you look at a statement of a high-level language you think about the effect
the statement will have on the environment of your program when it executes, you
do not think about the code that gets generated and then think about the
execution of that code.  Thus modeling semantics in terms of a compiler model is
addiing one more level of obfuscation.  A more natural description of the meaning of
constructs is given in terms of the run-time behavior of these constructs.
That's what LISP does.  The %3eval%* function describes the execution sequence of a
representation of an arbitrary LISP expression.  Thus %3eval%* is the semantic
description of LISP.  Now certain timid souls shrink from this resulting
circularity:  the description of the semantics of a language in that language, but 
circularity, like death and taxes, is inevitable.

Attempts have been made to give non-circular interpreter-based
descriptions of semantics for languages other than LISP.  There is the
incredible VDL description of PL/1; and the convoluted description of ALGOL 68
by a Markov algorithm.

To describe meaning in terms of 'self-evident' string manipulations
is misplaced rigor.  If a semantic description is to be anything more than a
sterile game it must be useful to implementors as well as applications
programmers.  If you decide to describe the semantics of language L%41%* in a
simpler language L%42%* then either L%42%* is 'self evident' or you must give a
description of the meaning of L%42%*, etc.  So either you go circular or you end
up with a (useless) 'self-evident' L%4n%*.

There are very good reasons for deciding on direct circularity.  First,
you need only learn one language.  If the semantic specification is given
the source language, then you learn the programming language and the
semantic (meta) language at the same time.  Second, since the evaluator is
written in the language, we can understand the language by understanding
the workings of the single program, %3eval%*; and if we wish to modify the
semantics we need change only one (source language) program.  Thus, if we
wished to add new language constructs to LISP (like the %3prog%* feature) we
need only modify %3eval%* so that it recognizes an occurrence of a (sexpr
representation of a) %3prog%*, add a new (semantic) function to describe the
interpretation of the construct and we're done.


A semantic description should not attempt to explain everything about a language.
You must assume that your reader understands something ... . McCarthy: %2`Nothing
can be explained to a stone'%*.

A semantic description of a language must be natural.  It must match the expressive
power of the language. A semantic description should also model how the constructs
are to be implemented on a reasonable machine.  What is needed is a semantic 
representation which exploits, rather than ignores, the structure of the language.
It can assume a certain level of understanding on the part of the
reader.  It need only explain what needs explaining.

Let's look at syntax for a moment.  A satisfactory description of much of
programming language syntax is standard BNF.  The BNF is a generative, or synthetic
grammar.  That is, rewriting rules specifying how to generate  well formed
strings are given.  A semantic specification on the other hand can be considered
to be a function which takes as input an arbitrary programs and gives as output
a representation of the value of executing the program.  This implies that
our semantic function must have some way of analyzing the structure of the program.


.P75:
In 1962, John McCarthy described the concept of abstract ⊗→analytic syntax↔←. It
is analytic in the sense that it tells how to take programs apart.. how to recognize
and select subparts of programs using predicates and selector functions.  It is abstract
in the sense that it makes no commitment to the external representation of the
constitutients of the program.  We need only be able to recognize  the occurrence
of a desired construct. For example:

←isterm[t]%c≡%*isvar[t]%c∨%*isconst[t]%c∨%*(issum[t]∧isterm[addend[t]]∧isterm[augend[t]])

and the BNF equation:

←<term> ::= <var> | <const> | <term> + <term>.

issum, addend, and augend, don't really care whether the sum is represented as:

x+y, or +[x;y] or %3(PLUS X Y)%* or xy+ .  The different external representations
are reflections of different ⊗→concrete syntax↔←es. The above BNF equations give one.

What is gained?  Since it is reasonable to assume that the semantics is to
operate on some internal representation of the source program, and in fact,
a representation reflecting the structure of the program (commonly known
as a parse tree), we can describe the semantics of a program in terms of a function
which operates on a parse tree using the predicates and selectors of the
analytic syntax. Abstract syntax concerns itself only with those properties
of a program which are of interest to an evaluator.

You may then profitably think of the Meta expression form of LISP as a concrete syntax.
You may think of the M- to S-expression translator as the parser which maps
the external representation onto a parse (or computational) tree. The selectors
and predicates of the analytic syntax are straightforward; recall the BNF for
LISP:

.BEGIN TABIT1(11);GROUP;

<form>\::= <constant>
\::= <variable>
\::=<function>[<arg>; ... <arg>]
\::= [<form> → <form> ... <form> → <form>]
\  ....

.END
Among other things, then, we need to recognize constants (%3isconst%*),
variables (%3isvar%*), conditional expressions (%3iscond%*), and functions 
(%3isfun%*).
We would then need to write a function in some language expressing the values
of these constructs. Since the proposed evaluator is to manipulate parse
trees, and since the domain of LISP functions %2is%* binary trees, it should seem
natural to use LISP itself.  If this is the case, then we must represent the parse
tree as a LISP sexpr and represent the selectors and  recognizers as LISP functions and
predicates.
Perhaps:

.BEGIN SELECT 3;TABIT1(11);GROUP;

isconst[x]\:numberp[x]%c∨%*eq[x;NIL]%c∨%*eq[x;T]%c∨%*eq[car[x];QUOTE]

isvar[x]\:atom[x]%c∧¬%*(eq[x;T]%c∨%*eq[x;NIL]%c∨%*numberp[x])

iscond[x]\:eq[car[x];COND]

.END

So to recapitulate, a concrete syntax for LISP can be conceived of as the normal Mexpr
notation; and abstract syntax for LISP can be formulated in terms of the representation of the
LISP program as a Sexpr.  The the description of the semantics of LISP is simply %3eval%*.

There are really two issues here: %2a%* representation of the analytic syntax of a language,
and a representation in terms of the language itself.  In conjunction, these two
ideas give a natural and very powerful means of specifying semantics.

If this means of semantic specification %2is%* really all that good (does
all good thing, no bad thing, and takes no time) then we should be able to 
specify other languages  similarly. What are the weak points of LISP as
`real' programming language?  Mainly the insistance on binary tree representations
of data.  It is quite clear that many applications could profit from other
data representations.  What we would then like is a language which has richer
data structures than LISP but which is designed to allow LISP-style semantic specification.
That is, we will be able to give an analytic syntactic specification for the language.
We will be able to write an evaluator, albeit more complex than %3eval%*, in the language
itself.  The evaluator will operate on a representation of the program as a legal 
data structure of the language, just as %3eval%* operates on the sexpr translation
of the LISP program.  The concrete syntax will be specified as a set of BNF equations,
and our parser will translate legal strings -- programs-- into parse trees.
In outline, to completely specify a construct in LISP we must have the following:

.BEGIN TABIT1(30);GROUP;

\%21.%*  A concrete production
  **1**\%22.%*  An abstract data type
\%23%*.  A mapping from %21%* to %22%*.
\%24.%*  An evaluator for the abstract type.

.END
The `real' programming language ⊗→EL1↔←, Extensible Language 1, %2has%* in fact been specified in exactly
this manner. We could not begin to describe this language here; rather we will
sketch only a bare outline of the ideas involved. As with LISP, EL1 maps programs
onto data structures. EL1 has richer data types including integers, characters, 
pointers, and structures. Its syntax is described in BNF and a mapping from
well-formed syntactic units to data structures is given. The EL1 evaluator
is written in EL1 and manipulates the data-structure representation of EL1 programs
in a manner totally analogous to the LISP %3eval%* function.

As the name implies, a rationale for EL1 was extensibility. 
An ⊗→extensible language↔← is supposed to supply a base or core language, which has
sufficient handles such that a user can describe new data structures, new operations,
and new control structures. These new  objects are  described in terms of 
combinations of constructs in the ⊗→base language↔←. Extensibility is implicitly
commited to the premiss that the power of high level languages is
primarily notational rather than computational. 
An alternative to extensibility, called ⊗→shell languages↔←, is perhaps
best exemplified by ⊗→PL/1↔←.

`Perhaps the most immediately striking attribute of PL/1 is its bulk'. "bulk"...
that's a polite word for another four-letter expletive.  If nothing else
PL/1 should have the beneficial effect of illustrating the absurdity
of languages which attempt to do all things for all people. ?? PL ... political 
language?? The sheer size of such languages bodes ill for efficient compilation,
maintanence, and learnability.
PL/1 also suffers for the "committee effect" in language design. No great work of art has
ever been designed "by committee"; there is no reason to believe programming language
design should be any different.

We have frequently seen how easy it has been to extend LISP by modifying %3eval%*.
This is particularly easy because we are making modifications at the level of data-structure represntation
of programs. In EL1 we wish to make the extensions at the level of concrete syntax, 
rather than abstract syntax as LISP does. 
We can do this by using a parser which is table-driven,
operating on an modifable set of productions. The parser must be capable
of recognizing occurrences of a set %21. - 4.%*  of **1** above, adding
%21%* to its set of productions, using %22%* and %23%* to effect the
translations, and using %24%* to effect the evaluation of an instance of %21%*.
This in essence is what EL1 does.
.SS(More on Compilation,compiler)
As we have described in previous notes the processes of evaluation
and compilation are parallel:  the evaluator performs the evaluation; the
compiler emits instructions which when executed produce the same computational
effect as the evaluator.  
Since the code produced by the compiler is either in  machine language
or in a form closer to the machine than the source program, we can execute
the code much faster. A speed-up factor of ten is not uncommon.
Also in LISP we know that programs are stored as sexpressions.
Our compiled code will be machine language, thus freeing a large quantity
of sexpression storage. This will usually make garbage collection 
be less time consuming.
Why not compile all programs? We already have seen that we can %3cons%*-up
new expressions to be evaluated while we are running. Still we can force
even those expressions through a compiler before execution. The answer,
rather, is that for debugging and editing of programs it is extremely convenient
to have a structured representation of the program (like sexpression)
in memory. We shall say more about this later.

We shall exploit the analogy between compilers and evaluators when we write the
LISP function, ⊗→%3compile%*↔←, which will describe the compiler.
We shalll do this in two ways. First, the structure of the %3compile%* function
and its subfunctions will be written to capitalize on the knowledge we
have acquired from writing evaluators. Second and more difficult, we will attempt
to abstract from the specific compiler, the essence of LISP compilers without
losing all of the details. At the most general level a compiler simply
produces code which when executed has the same effect as evaluating the original
form, but this description has lost too much detail.
This second task is more difficult because we have to separate two representations
from the specific compiler. We are rrepresenting forms as data structures; and we
are also dealing with the representation of a specific machine.
The task %2is%* worth persuing since we wish to write different compilers
for the same machine and also  a single compiler capable of easy transportation to
other machines. 

The input to
%3compile%* is the sexpr representation of a LISP function; the output is a list
which represents a sequence of machine instructions.  Assume that we have
LISP running on %aBrand X%* machine, and we have just written the LISP function,
%3compile%*, which produces code for %aBrand X%* machine. Then:
.GROUP

	1.  Write the Sexpression form of %3compile%*.

	2.  Read in this translation, defining %3compile%*.

	3.  Ask LISP to evaluate:  %3compile[COMPILE]%*.
.APART

Now since %3compile%* is a function of one argument which proports to compile code
for %aBrand X%* machine, translating the sexpression representation of its argument
to machine code, the output of step 3. should be a list of instructions 
representing the translation of the function %3compile%*.  That is, step 3. compiles
the compiler!!

A technique called %2⊗→bootstrapping↔←%* is closely related to the process described
above. Assume that we have LISP and its compiler running on %aBrand X%*, and
we wish to implement LISP (quickly) on %aBrand Y%*. If we have been careful in
our encoding of the %3compile%* function then %2most%* of %3compile%* is
machine independent, that is it deals mostly with the structure of LISP and
only in a few places deals with the structure of the particular machine.  As we
will see this is not too  great an assumption to make.
Notice that this is one of our admonitions:  encode algorithms in a 
representation-independent style and include representation-dependent
rountines to interface with the program. To change representations, simply
requires changing  those simpler subfunctions. Here the repesentations are
machines and the algorithm is a compiling function for LISP.

Let us call those parts of the compiler
which deal with the machine, the ⊗→code generators↔←. Now if we understand the
machine organization of brands %aX%* and %aY%* then for any instruction on %aBrand X%*
we should be able to give a (sequence of) instructions having the equivalent
effect on %aBrand Y%*. In this manner we can change the code generators in %3compile%*
to generate code to run on %aBrand Y%*. We thus would have a %3compile%* function,
call it %3compile*%*, running on %aX%* and producing code for %aY%*.
Now if we take the Sexpr forms of %3eval, apply, read, print, compile,...%* etc.
and pass these functions through %3compile*%*, we will get a large segment
of a LISP system which will run on %aY%*. Certain primitives will have to be
supplied to run this code on %aY%*, but a very large part of LISP can be
bootstrapped from %aX%* to %aY%*.

Obviously, before we can use %2a%* compiled version of the compiler (or
in fact, before we can use any compiled code) we must have some means of
translating the list output of the compile function into real instructions in the
machine.  So if the version of LISP which we are implementing is to have a
compiler we must allocate an area of memory which can receive the compiled code.
This area is usually called %2⊗→Binary Program Space↔←%* (BPS).  The translation program
which takes the list of output from the compiler and converts it onto actual
machine instructions for ⊗→BPS↔← is called an assembler. Before discussing ⊗→assemblers↔←
we will  examine a sequence of simple compilers corresponding to the LISP
subsets evaluated by ⊗→%3tgmoaf%*↔←, ⊗→%3tgmoafr%*↔← and finally an ⊗→%3eval%*↔← which
handles local variables.

.SS(Compilers for subsets of LISP)

We will examine  compilers for increasingly complex subsets of LISP
beginning with functions, composition and constant arguments and
ending with a more realistic compiler for a reasonable subset of
pure LISP. Though each subset is a simple extension of its predecessor,
each subset introduces a new problem to be solved by the compiling algorithm.
If the corresponding evaluator (⊗→%3tgmoaf%*↔←, ⊗→%3tgmoafr%*↔← and the most
simple ⊗→%3eval%*↔←) is well understood, then the necessary steps
to be added to the compiler are easy to make.

First we need to begin describing a list of conventions which will remain in
effect through out this sequence of compilers.  The code which is generated
must be compatible with that which incorporates the basic LISP machine.
In particular the calling conventions for function invocation must be
maintained.  Thus a function of %3n%* arguments expects its arguments to
be presented in AC1 through ACn. Also the execution of any code which is
computing arguments to a function call must store temporary results on the stack,
%3P%*. Thus the execution sequence of code for computing %3n%* arguments
should be: 

.BEGIN centerit;
←compute value of argument%41%*, push onto stack, %3P%*.

←..........
←compute value of argument%4n%*, push onto stack, %3P%*.
.END

So after this computation the values of the arguments are stored
V%4n%*, V%4n-1%*, ..., V%41%*, from top to bottom in %3P%*.
Thus to complete the function invocation, we need only pop the arguments
into the AC's in to obvious order. This brings us to the last 
(and the most important!) convention for the initial compiler. 
We must always be sure that the integrity of the stack is maintained. What ever
we push onto the stack within the body of a function %6must%* be
popped off before we exit from the function body. That is, the state of the stack
must be transparent to any computations which occur within the function.
The first compiler will handle (the S-expression translation of) that
subset of LISP forms defined by the following BNF equations:

.BEGIN TABIT1(11);GROUP

<form>\::= <constant> | <function>[<arg>; ...; <arg>] | <function> [ ]

<arg>\::= <form>

<constant>\::= <sexpr>

<function>\::= <identifier>

.END

This LISP subset corresponds closely with ⊗→%3tgmoaf%*↔←, handling only
function names, composition, and constant arguments.
Our previous compiling conventions will keep us in good stead. 
We need only consider the compilation of constants. A S-expression
constant will be seen as  %3(QUOTE ...)%* by the compiler. The
code which we wish to generate is:


.BEGIN TABIT1(30);SELECT 3;GROUP

\(MOVEI AC1 (QUOTE ...))
.END
It should now be clear how to proceed with the first compiler.

.BEGIN SELECT 3;TABIT2(11,18);
.GROUP

compexp <=\λ[[exp]\[eq[car[exp];QUOTE] → list[list[MOVEI;AC1;exp]];
\\ T → compapply[car[exp];complis[cdr[exp]];length[cdr[exp]]]] ]
.APART
.GROUP

complis <=\λ[[u]\[null[u] → NIL;
\\ T → append[compexp[car[u]];((PUSH P AC1));complis[cdr[u]]]] ]
.APART

.P82:
compapply <= λ[[fn;args;n]append[args;loadac[n];list[list[CALL;n;list[E;fn]]]]]

.APART
.P56:
.GROUP
loadac <=\λ[m]\[zerop[m] → NIL;
\\ T → cons[list[POP;P;cdr[assoc[n;aclist]]];loadac[n-1]] ]

%1where:%* aclist %1is%* ((1 . AC1) ... (N . ACn)).

.END
Notice that the actual function call generated by %3compapply%* is of the
form:

←%3(CALL%* n%3(E%* name%3))%1

The %3E%*-construct is discussed in the next section on assembling.

The code generate by this compiler is clearly inefficient, but that
is not the point. We wish to establish a correct compiler, then later 
worry about efficiency.

The innovation which occurred in %3tgmoafr%* was the apprearance of conditional 
expressions. To describe conditional expressions, the above BNF equations
were augmented by:

←<form> ::= [<form> → <form> ; ... <form> → <form>]

Certainly the addition of conditional expressions will mean an extra 
piece of code in %3compexp%*
to recognize %3COND%* and a new function (analogous to %3evcond%* in %3tgmoafr%*)
to generate the code for the %3COND%*-body.
In fact, the only difference between %3evcond%* and its counterpart in 
%3compexp%*, which we shall call %3comcond%*, is that %3comcond%* generates
code which when executed will produce the same value as the value
produced by %3evcond%* operating on the given S-expression.

The effect of %3comcond%* on a conditional of the form:

(%2*1*%*)←%3(COND (%1p%41%* e%41%3) ... (%1p%4n%* e%4n%3))%1 should be clear.

First generate code for p%41%*; generate a test for truth, going to the
code for e%41%* if true, and going to the code for p%42%* if not true.
The code for e%41%* must be followed by an exit from the code for the
conditional, and we should probably generate an error condition to be executed
in the case that p%4n%* is false.

.BEGIN NOFILL;GROUP;
Pictorially, we might represent the code as:

		<code for p%41%*>




 
	        T			NIL


	<code for e%41%*>		<code for p%42%*>


				     T			NIL


		<code for e%42%*>		        <code for p%43%*>

		     ....          			....



					     T			NIL
	

				<code for e%4n%*>		<code for error>






.END

This requires the establishment of more conventions for our compiler.
In particular we must be able to test for %3T%* (or %3NIL%*). We will
define %3NIL%* to be the zero of the machine, and we will test for
%3NIL%* using the %3JUMPE%* instruction
(see {yonss(P33)}). Next, since our code is to be a %2sequence%* of instructions,
we must linearize this graph representation of the generated code.
Thus  for the compilation of *1*, above,
we will generate:

.BEGIN TABIT2(30,35);GROUP

\%3(\%1<code for p%41%*>%3
\\(JUMPE AC1, L1)%1
\\<code for e%41%*>%3
\\(JRST L)
\L1\%1<code for p%42%*>%3
\\(JUMPE AC1, L2)
\        ...
\Ln-1\%1<code for p%4n%*>%3
\\(JUMPE AC1, Ln)%1
\\<code for e%4n%*>%3
\\(JRST L)
\Ln\(JRST ERROR)
\L\   )
.END
%1

To generate such code we need to be able to generate the labels, %3Li%*.
The generated labels should be atomic and should be distinct. LISP has
a function, ⊗→%3gensym%*↔←, which can be used for this task. %3gensym%*
is a function of no arguments  whose value is a generated symbol or atom
which is guaranteed to be distinct from any atom generated in any of
the usual manners. In many versions of LISP, gensyms are of the form
%3Gn%* where %3n%* is a four digit number beginning at %30000%*. Thus
the first call; %3gensym[ ]%* would give %3G0000%*; succeeding calls would give
%3G0001, G0002%*, etc.
First, gensyms are not placed in the object list since
they are usually used only for their unique name. Second, if you explicitly
place them in the symbol table they are obviously distinct from each other and
will be distinct from all other atoms unless, of course, you read in such an atom.

Without too much difficulty we can now add the recognizer for
%3COND%* to %3compexp%* and construct %3comcond%*.

.BEGIN SELECT 3; TABIT3(27,34,45);TURN OFF"←";GROUP;
.FILL

%1Add%* eq[car[exp];COND] → comcond[cdr[exp];gensym[ ]]; %1to%3 compexp 
%1where:
.NOFILL
%3

comcond <= λ[[u;l][prog[[z]\z ← gensym[ ];
\return[\[null [u] → list[(JRST ERROR);l]:
\\ T → append\[compexp[caar[u]];
\\\ list[list[JUMPE;AC1;z]];
\\\ compexp[cadar[u]];
\\\ list[list[JRST;l]z];
\\\ comcond[cdr[u];l]]]]
.END
%1

.BEGIN GROUP;TABIT2(30,38);
The partially exposed recursive structure of %3comcond%* would show:

←%3comcond[((%1p%41%*  e%41%3) ...(%1p%4n%*  e%4n%3));G0000]=

\%3(%1\<code for p%41%*>%3
\\(JUMPE AC1, G0001)%1
\\<code for e%41%*>%3
\\(JRST G0000)
\ G0001\comcond[((%1p%42%* e%42%3) ...(%1p%4n%* e%4n%3))])

.END

%1
So the second argument to %3comcond%* is a generated symbol to reflect the
label attached to the end of the conditional  statement. There is
another  generated name  used "locally" to %3JUMPE%* from p%4i%* to
p%4i+1%*.

Before attacking the major problem of our compilers, the handling of
variables, we shall describe how the list representing the output
of the compiler is turned into code which runs on the machine.


.SS(Problems)

.BEGIN TABIT1(16);
I. Evaluate: 
%3compexp[(COND(\(EQ (QUOTE A)(QUOTE B))(QUOTE C))
\((NULL (QUOTE A))(QUOTE FOO))))]


****more, more ****

.END
.SS(One-pass Assemblers,assemblers,P7:)

Define %3compile%* as:

%3compile <= λ[[fn;vars;exp]append[list[list[LAP;fn;SUBR]];compexp[exp]]]%*.

Consider the output from %3compile%* for the function:
.GROUP

%3←j [] <= f[g[A];h[B]]%* 

or more precisely, for the evaluation of

←%3compile[J;();(F(G(QUOTE A))(H(QUOTE B)))]%*.
.APART
.GROUP

It would be a list of the form:
.BEGIN TABIT2(10,45);SELECT 3;
\((LAP J SUBR)\%1; says %3j%* is a function%3
\(MOVEI AC1(QUOTE A))\%1; make argument for call on %3g
\(CALL 1 (E G))\%1; call the function%3
\(PUSH P AC1)\%1; save the value%3
\(MOVE AC1(QUOTE B))
\(CALL 1 (E H))
\(PUSH P AC1)
\(POP P AC2)
\(POP P AC1)
\(CALL 2(E F))
\(POPJ P)
\)

.END
.APART
%1

As you know the machine representation of these instructions are encodings of
specific fields of specific machine locations with specific numbers.
For example, the operation %3PUSH%* is represented as a certain number,
called its %2⊗→operation code↔←%* or %2op code%*, and which will
occupy a certain area of a machine word so that the CPU can interpret
it as an instruction to push something onto a stack.  Other fields in the
instruction are to be interpreted as references to stacks, to memory locations,
to accumulators, constnats or external references to other routines.
The purpose of an assembler is to translate these mnemonic instructions
into raw seething machine instructions.

Essentially all that the assembler need do is search ⊗→symbol tables↔←
for the opcodes, for subroutine names, for accumulator and stack names,
and store the resulting values in the appropriate machine locations.

Things are slightly more complex: we must also %6add%* information to
the tables as we proceed.  For example, as we assemble the code for a new
routine we must add its name and starting address to the current symbol
table.  The phrase, %3 (LAP %1name%3 SUBR)%* does this.

We must exercise a bit of care in handling  %3QUOTE%*d expressions.
Assembling a construct like %3(MOVEI AC1 (QUOTE (A B C)))%* should
have the effect of constructing the list %3(A B C)%* in free space
and placing an instruction in memory to load the address of this list into AC1.
What we must notice is that this list %3(A B C)%* is subject to
garbage collection and, if left unprotected, could be destroyed.
There are a couple of solutions. Perhaps the garbage collector could
look through compiled code for any references to free- or full-word- space;
or we could make a list of all of these constants and let the garbage
collector mark the list.

Much more problematic is the handling of labels and references to labels.
This case arose in the compiler for ⊗→%3tgmoafr%*↔← when we introduced
conditional expressions. Recall that the code for a ⊗→conditional expression↔←
of the form:

.GROUP
%3←(COND (%1p%41%* e%41%3) ... (%1p%4n%* e%4n%3)) %1 was:

.BEGIN TABIT1(35);

\    <code for p%41%*>
\    %3(JUMPE AC1 L1)%1
\    <code for e%41%*>
\    %3(JRST L)
\L1  %1<code for p%42%*>
\    %3(JUMPE AC1 L2)%1

\          ....
\    <code for e%4n%*>

\%3L        ....

.END
.APART
%1

The symbols, %3 L, L1,%* and %3L2%* in this example are labels.  Notice
that if we were to consider writing the assembler in LISP,
we could distinguish occurrences of labels from instructions using
the predicate, %3atom%*.

It perhaps is time to start thinking about writing such an assembler.
One of the arguments to the function should be the list representation
of the program.  One of its arguments should also describe where (in ⊗→BPS↔←)
we wish the assembled code to be located. We should also have access
to an initial symbol table, describing the opcodes and pre-defined
symbol names. Let's call the function, ⊗→%3assemble%*↔←.
%3assemble%* then can go %3cdr%*-ing down the program list, looking up
definitions and manufacturing the numerical equivalent of each 
instruction, then depositing that number in the appropriate machine
location.  If %3assemble%* comes across a label definition, it should
add information to a symbol table, reflecting that the label has
been seen and that it is associated with a specific location in memory.
Then future references to that label can be translated to references
to the associated machine location.  The only problem is that references
to labels may occur %6before%* we have come across the label definition 
in the program.  Such references are called %2⊗→forward reference↔←s%*.

.GROUP
For example, consider the following nonsense program:

.BEGIN TABIT1(35);SELECT 3;

\(  (LAP FOO SUBR)
\ X (JRST X)
\    (JRST Y)
\ Y (JRST X) )

.END
.APART
The reference to %3Y%* is a forward reference; neither of the references to %3X%*
is forward since %3X%* is defined before being referenced.


There are two solutions to the ⊗→forward reference↔← problem:

.BEGIN INDENT 0,5;
%21.%*  Make two passes through the input program.  The first pass
decides where the labels will be assigned in memory.  That is, this
pass builds a symbol table of labels and locations.  Then a second pass
uses this symbol table to actually assemble the code into the machine.
This works, but is not particularly elegant. It is expensive to read through
the input twice, particularly when we can do better.

%22.%*  The other solution is to make one clever pass through the input.
Whenever we come across a forward reference we add information to the symbol table
telling that a forward reference has occurred at this location.  We assemble
as much of the instruction as we can.  When a label definition %6does%*
occur we check the table to see if there are any forward references pending
on that label.  It there are such we  %6⊗→fix-up↔←%* those instructions to
reference the location now assigned to the label.

.END
A speed-up by a factor ranging from two to five is not uncommon for a good
one pass assembler.
There are some restrictions which are imposed on one-pass assemblers, but
particularly for assembling compiled code, one-pass assemblers are quite sufficient.


There are at least two ways to handle fixups and forward references.  If
the fixups are of a particularly simple nature, say only requiring fixups
to the address-part of a word, then we may link those pending forward references
together, chaining them on their address parts. Thus:

.GROUP SKIP 20;

Another solution, which is potentially more general (that is, it could
handle left-half, right-half or partial-word fixups) is to store the information
about each fixup in the symbol table under each label. Thus:

.GROUP SKIP 20;

Both methods are useful. Both have been used extensively in assemblers and
compilers.

To write the function, %3assemble%*, we will need two functions:
.BEGIN INDENT 0,10;

%21.%*  ⊗→%3deposit%*↔←%3[x;y]%*: %3x%* represents a machine address; %3y%* is a list,
representing the instruction to be deposited. %3y%* should be a list of
four elements: %3(%*opcode ,accumulator number, memory address, index register%3)%*
The value of %3deposit%* is the value of %3y%*.

%22.%*  ⊗→%3examine%*↔←%3[x]%*: %3x%* represents a machine address.  The value
of %3examine%* is the contents of location %3x%* in the form of a list as
specified above.
.END
.BEGIN TURN ON "#";

%3assemble%* needs to recognize that there are different instruction formats.
That is,some instructions use an opcode and a memory reference: %3(JRST#L)%*;
some use an opcode, accumulator, and an address: %3(PUSH#P#AC1)%*; and some
vary: %3(MOVE#AC1#(QUOTE A))%* and %3(MOVE#AC1#-1#P)%*. %3assemble%* also
has to have an initial symbol table of opcodes, accumulator numbers, and
stack numbers:
.END

.BEGIN TABIT2(35,45);GROUP;
%2\symbol\value%3
\MOVE\200
\MOVEI\201
\SUB\274
\JRST\254
\JUMPE\322
\JUMPN\326
\PUSH\261
\POP\262
\POPJ\263
\CALL\034
\AC1-n\1 - n
\P\14
.END

.GROUP
So for example:

←%3assemble[((LAP FOO SUBR) X (JRST X) (JRST Y) Y (JRST X));104]%* should

have the final effect:
.BEGIN TABIT1(43);

--→%7α~~~]%*--→%bPNAME%7[~~[~~]%1--→%7[~~]~~]%*--→%bSUBR%7[~~[~~]%1...
\|
\|
\|
\|        op   ac  ind  add
\→104  254    0   0   104
\  105  254    0   0   106
\  106  254    0   0   104

.END
.APART
.SS(A compiler for simple %3eval%*,compiler,P32:)

Consider the function defined by:

←%3j[x;y] <= f[g[x];h[y]]%*

We claim that the following code suffices for function:
.BEGIN TABIT2(10,45);SELECT 3;

\(LAP J SUBR)\%1; says %3j%* is a function%3
\(PUSH P AC1)\%1; save the input args%3
\(PUSH P AC2)
\(MOVE AC1 -1 P)\%1; get %3x
\(CALL 1 (E G))\%1; call the function named %3g
\(PUSH P AC1)\%1; save the value%3
\(MOVE AC1 -1 P)\%1; get y%3
\(CALL 1(E H))\%1; call %3h
\(PUSH P AC1)
\(POP P AC2)\%1; restore the arguments in%3
\(POP P AC1)\%1;   preparation for%3
\(CALL 2(E F))\%1;   calling %3f
\(SUB P(C 0 0 2 2))\; %1sync the stack; remove the saved args%3
\(POPJ P)\; %1exit.%3 AC1%* still has the value from %3f.
\   )
.END
Here is a picture of the execution of the code:

.BEGIN TURN ON "\";NOFILL;TABS 5,10,25,30,45,50,65,70;SELECT 3;GROUP;

AC1: x ; AC2: y

\|\| (PUSH P AC1)\\ (PUSH P AC2)\|  y\|(MOVE AC1 -1 P)\| y | (CALL 1 (E G))
\|\|    =>\|  x\|     =>\|   x\|        =>\| x |  =>


AC1: g[x] ; AC2: ?\\\AC1: y ; AC2: ?
\\ (PUSH P AC1)\|g[x]\|(MOVE AC1 -1 P)\|g[x]\| (CALL 1(E H))
\|  y\|      =>\|  y\|      =>\|  y\|   =>
\|  x\|\|  x\|\|  x\|


AC1: h[y] ; AC2: ?\\\AC2: h[y]\AC1: g[x] ; AC2: h[y]
\|g[x]\| (PUSH P AC1)\|h[y]\|   (POP P AC2)\|g[x]\|  (POP P AC1)\| y |(CALL 2 (E F))
\|  y\|       =>\|g[x]\|      =>\|  y\|      =>\| x |   =>
\|  x\|\|  y\|\|  x\|
\    \ \|  x\|


AC1: f[g[x];h[y]]
\|  y\|(SUB P (C 0 0 2 2))\\|\| (POPJ P)
\|  x\|           =>    \=>


.END

.BEGIN INDENT 0,10;TURN ON "#";
Notes: The %3(MOVE %*x -n%3 P)%1 instruction allows us to put a copy
of the contents of the n%8th%* element down the stack.  Notice too, that
the addressing in the code is relative to the top of the stack: %3(MOVE#AC1#-1#P)%*
gets us %3x%* in one instance and gets us %3y%* in another, because the top 
of the stack changes.
.END

Clearly we want a compiler to produce equivalent (albeit inefficient) code.
Once we understand how to do this it is relatively easy to improve on the efficiency.
We shall now extend %3compile%* to handle local variables.



.<<discussion of offset and vpl>>
.BEGIN TURN ON "#";
	The major failing of the previous %3compile%* is its total lack of
interest  in variables.  This is  a  non-trivial problem  which every
compiler must  face.    You  have just seen an example  of  plausible  code
generation for simple LISP functions, in particular:

←%3j[x;y] = f[g[x];h[y]]%*

The crucial point is how to generate code which `knows'
where on  the stack we can find the value  of a (local) variable when
we execute that code.  What  we shall do is simulate the behavior  of
the runtime  stack while  we are  compiling the  code.   The compiler
cannot  know what the %2values%* of the  variables will be at runtime but
we claim that it should know %3where%* to find the values.  We will carry
this information through the  compiler in a manner reminiscent of the
`dotted-pair' symbol table of the first version of %3eval%* seen in {yonss(P6)}.  Instead  of
posting the current values  in the stack, the compiler  will post information about  the
positions  of the variables relative  to the top of  the stack at the
time we enter  the function.   The variable %3vpl%*, for variable pair list,
contains this information.  That is if we are
to compile  a function with λ-variables, %3[x;y;z]%* then %3vpl%* will begin
with:

←%3((X . 1), (Y . 2), (Z .3) ...%*

When we set up %3vpl%* 
we also set the %2⊗→offset↔←%*,  called %3m%*, to minus the number  of args added
to %3vpl%*. (In this  case -3).  Now if we come across a reference say to
%3Y%* while compiling code, we  use %3cdr[assoc[Y;vpl]]%* to retrieve %32%*.   The
offset plus this retrieved value gives  us the relative position of %3Y%*
in  the stack.   I. e.,  -3 +  2 = -1.   Thus  to refer  to the stack
location of %3Y%*  we could  use %3(....-1#,#P)%*.  What  happens as we  add
elements to  the stack? (Or to  be more precise...what  happens as we
generate code which when  executed will add  elements to the  stack.)
Clearly we must modify the  offset.  If we add one  element, we would
set  %3m%* to -4.   Then to reference  %3Y%* now use  -4 + 2  = -2.   I. e. a
reference to %3Y%* is now of the form:

←%3( ......-2 P).%*

But that's right.  %3Y%*  is now further down in the run time  stack.  So
to  complete the analogy, the  `symbol table' is really  defined by %3m%*
plus the  current  %3vpl%*.

When will the compiler make modifications  to the top  of the stack?   First, we
push new  elements when we are compiling  the arguments to a function
call.  The function  in the new compiler which compiles the  argument
list is called %3complis%*:

.BEGIN SELECT 3; TABIT2(22,32);GROUP

complis <= λ[[u;m;vpl]\[null [u] → NIL
\ T → append\[compexp [car [u]; m; vpl];
\\ ((PUSH P AC1));
\\ complis [cdr [u]; m-1; vpl]]]
.END

Notice  that   %3complis%*  compiles  the   arguments  from  left   to  right,
interspursing  them with %3(PUSH#P#AC1)%* and recurring with  a new offset
reflecting the effect of the %3PUSH%*. Clearly this function is analogous to
%3evlis%*.

Here's a brief description of the parts of the new compiler. This compiler was 
adapted from one written
by John McCarthy in conjunction with a course at Stanford University
entitled %3Computing with Symbolic Expressions%*. The McCarthy compiler
was also the subject of study by Ralph London in his paper,
%3Correctness of Two Compilers for a LISP Subset%*.

.BEGIN INDENT 0,15;
%3compile[fn;vars;exp]: fn%* is  the name of  the function to be  compiled. %3vars%*  is the
list of lambda variables.  %3exp%* is the lambda-body.

%3prup[vars;n]:  vars%* is  a  lambda list, %3n%* is an  integer.   %3prup%*  builds  a
variable-pair list.

%3mkpush[n;m]%*:  generates a sequence of %3PUSH%* instructions.

%3loadac[n;k]%*:  is a slight modification of the previous %3loadac%* ({yon(P56)}).
This version generates a series of %3(MOVE ACi ...)%* instructions followed
by a %3(SUB P (C 0 0 N N))%*, rather than a sequence of %3POP%*s.

%3compexp[exp;m;vpl]%*: this  function does most  of the work.   It is  analogous to
%3eval%*.
It generates the code for constants,
for a reference to a variable,
and for conditional expressions.
It is  used for compiling code for  a call on a function,
compiling the argument list with %3complis%*, which will
leave the arguments in the stack; %3loadac%* loads the  appropriate %3AC%*'s.
and then we generate the %3SUB%*  to sync the stack, and finally generate
a call on the function.

%3comcond[u;m;l;vpl]%*: this compiles the body of conditional expressions.  %3u%* is the
p%4i%* - e%4i%*  list; %3l%* will be  bound to a  generated symbol name
; %3m%* and %3vpl%* are as always.
.END
.END

Fortified by the previous %3compile%* functions and this introduction
the new %3compile%* should be clear.

.BEGIN NOFILL ;select 3;TURN OFF "←";

.GROUP
compile <= λ[[fn;vars;exp]
	    prog[[n]
	       n ← length [vars];
	    return [append [list[list [LAP;fn;SUBR]];
			   mkpush [n;1];
			   compexp [exp; -n; prup [vars;1]]
			   list [list [SUB;P;list [C;0;0;n;n]]]
			   ((POPJ P)) ]]]

.APART
.GROUP
prup <= λ[[vars;n] 
	  [null [vars] → NIL;
	   T → cons [cons [car [vars]; n]; prup [cdr [vars];n+1]]]

mkpush <= λ[[n;m]
 	    [lessp [n;m] → NIL
	     T → cons [list [PUSH;P;cdr[assoc[m;aclist]]]; mkpush [n;m+1]]]


.APART
.GROUP
loadac <= λ[[n;k]
            [greaterp[n;0] → NIL;
             T → cons[list[MOVE;cdr[assoc[k;aclist]];n;P];loadac[n+1;k+1]]]]

.APART
.GROUP

compexp <= λ[[exp;m;vpl]
	     [null [exp] → ((MOVEI AC1 0));
	      or [eq [exp;T]; numberp [exp]] → list [list [MOVEI;AC1;list [QUOTE; exp]]];
	      atom [exp] → list [list [MOVE;AC1;m + cdr [assoc [exp;vpl]]; P]];
	      eq [car [exp]; COND] → comcond [cdr [exp]; m; gensym [ ]; vpl];
	      eq [car [exp]; QUOTE] → list [list [MOVEI;AC1;exp]];
	      eq [atom [car [exp]] → λ[[n]append [complis [cdr [exp];m;vpl]
				 	          loadac [1-n;1];
       ⊗↓%1This is sufficiently mysterious to warrant explanation.
  The "%3λ[[n]#...#][length[cdr[exp]] %*" is an internal λ-expression 
of one argument,
analogous to the call on %3compapply%* in the first compiler ({yon(P82)}).←%3
					          list [list [SUB;P;list [C;0;0;n;n]]
						     list [list [CALL;n;
							     list [E; car [exp]]]]]
				     [length [cdr [exp]]]]]

.APART

.GROUP

comcond <= λ[[u;m;l;vpl]
	     [null [u] → list[l];
	      T → λ[[l1] append [comexp [caar [u];m;vpl];
				list [list[JUMPE;AC1;l]];
     ⊗↓%1The same trickery used here as in %3compexp%*: %3l1%* is bound 
to the value of %3gensym[ ].%1←%3
			        compexp [cadar [u];m;vpl];
			        list [list [JRST;l];l1]
			        comcond [cdr [u];m;l;vpl]]]
		gensym [ ]]


.APART
.END


Here is a partial sketch of %3compile%* operating on %3j <= λ[[x;y]f[g[x];h[y]]].%*

.BEGIN SELECT 3;TABIT2(10,17);CENTERIT;

.GROUP
compile[J;(X Y);(F (G X) (H Y))] %1gives:%*
\append\[((LAP J SUBR));      (**1**)
\\ mkpush[2;1];
\\ compexp[(F (G X)(H Y));-2;prup[(X Y);1]];
\\ (SUB P (C 0 0 2 2))
\\ ((POPJ P ))];%1
.APART

.GROUP
where:
←%3mkpush[2;1]%* gives %3((PUSH P AC2)(PUSH P AC1)),%* and
←%3prup[(X Y);1]%* gives %3((X . 1)(Y . 2))%*.
.APART
.GROUP

%3compexp[(F (G X)(H Y));-2;((X . 1)(Y . 2))]%* results in:
%3
\append\[complis[((G X)(H Y));-2;((X . 1)(Y . 2))];
\\loadac[-1;1];
\\((SUB P (C 0 0 2 2)));
\\((CALL 2(E F)))]

%1and %3loadac[-1;1]%* evaluates to: %3((MOVE AC1 -1 P)(MOVE AC2 0 P))%*.
.APART
.GROUP

Thus (**1) above, is of the form:

%3
\\((LAP J SUBR)
\\ (PUSH P AC2)
\\ (PUSH P AC1)
\\ complis[((G X)(H Y));-2;((X . 1)(Y . 2))]
\\ (MOVE AC1 -1 P)
\\ (MOVE AC2 0 P)
\\ (CALL 2 ( E F))
\\ (SUB P (C 0 0 2 2))
\\ (POPJ P)
\\)

.APART
.FILL;
%3complis%1 is interesting since it actually uses the %3vpl%* we have been
carrying along. It gives rise to:
.NOFILL
.GROUP

%3
\append\[compexp[(G X);-2;((X . 1)(Y . 2))];
\\ ((PUSH P AC1));
\\ complis[((H Y));-3;((X . 1)(Y . 2))]]

.APART
.GROUP
%1and the %3compexp%* computation involves, in part:

%3
\append[complis[(X);-2;((X . 1)(Y . 2))];
\\ ((MOVE AC1 0 P));
\\ ((SUB P (C 0 0 1 1));
\\ ((CALL 1 (E G))]

.APART
.GROUP
%1Finally this %3complis%* generates the long awaited variable reference using:

%3compexp[X;-2;((X . 1)(Y . 2))] %1giving,
\\%3((MOVE AC1 -1 P))%*.
.APART

Notice that the offset is different within the call:

←%3 complis[((H Y));-3;((X . 1)(Y . 2))].%1

Finally, you should convince yourself that the code, though inefficient, is correct.
.END
.APART

←%2Problems%*

I  Simple problems

1. Evaluate %3compile[%1  h.s.] 
etc.

2. Complete the code generation for the above example.


.SS(A project: Efficient compilation)
.P35:
Certainly the most striking feature of the last %3compile%* is its
outrageous inefficiency. Examination of the compilation of the
most simple function suggests many possible improvements. 

We should first clarify what we mean the efficiency in this context.
We might mean minimal compile-time. In this case we would want a very
simple compiler; this usually means that the complied code is extraordinarily
bad. Such compilers might suffice for debugging runs or student projects.
More likely, efficiency compilation is taken to mean production of
code which we could expect from a reasonably bright machine-language programmer.
It should run reasonably fast, not have obviously redundant instructions, and
not take too much space in the machine. It is this second interpretation
of efficiency which we shall use.

A major inefficiency occurs in saving and restoring  quantities on the
stack. For example, the sequence %3(PUSH P AC1)(POP P AC1)%* serves no
useful purpose. This is a symptom of a more serious disease. 
The compiler does not remember what will be in the ACs at run-time. Since the
arguments to a function call must be passed through the special AC registers
and since it is expensive to save and restore these registers, we should
make a concerted effort to remember what quantities are in which ACs and
not reload them unnecessarily. This process will certainly  make the
compiler more complicated and that will mean longer compilation time but
compilation usually occurs less frequently than execution of compiled
code.

Here are some possibilities.

****ADD 'EM*****


diatribe about go to
A major obstacle to  this kind of optimization is the unrestricted use
of labels and gotos. Consider a piece of compiler code which has a label attached
to it.
 Before we can be assured of the integrity of an AC
we must ascertain that every possible path to that label maintains that AC.
This is a very difficult task. The label and goto structure required by
%3compile%* is quite simple. However if we wished to build a compiler for
LISP wirh %3prog%*s we would have to confront this problem.
.SS(A project: One-pass assembler)
.P10:

III A one-pass ⊗→assembler↔←.

Write a one-pass assembler for the code generated by the %3compile%* function
of this section. You should be aware of the following points:

.BEGIN INDENT 0,5;

%2a.%*  %3QUOTE%*d expressions must be protected from garbage collection. The
simplest way to accomplish this it to  save them on a list, say %3QLIST%*.

%2b.%*  Use the operation codes of {yonss(P7)})
****MORE ON INST FORMAT.***

%2c.%*  Design a simple fixup scheme.  Notice that %3compile%*'s code will
require address fixups at most.

%2d.%*  Recall that the format of the code is a list. The items in the list are
either atomic -- representing labels --, or lists -- representing instructions--.
The instructions have varying format.  Perhaps a ⊗→table-driven↔← scheme can be used.

%2e.%*  Some attempt should be made to generate error messages.

%2f.%*  Many of the constants, %3(C 0 0 %*n n%3)%*, occur frequently; these constants
are only referenced, never changed by execution of the compiled code.  Write
your assembler to maintain only one copy of each. The constants should be stored
directly after the compiled code.  

%2f%*.  Try to be equally clever about storing %3QUOTE%*d expressions.
.P36:

IV ***problem on internal lambdas

.END
.SS(A project: Syntax directed compilation,syntax-directed,P4:)

compilation for sae

BNF for mexprs

syntax directed compiler

scanner parser
.SS(A deep-binding compiler,deep binding)

**sketch of tgmoaf deep binder conventions

**project: do tgmoafr and eval d-b compr

**hints about globals and name stack

**project: do eval compiler using name-value stack for locals.

.SS(Compilation and global variables,global variables,P5:)
.BEGIN TURN ON "#";

**** expand greatly***

The models of compilation which we have sketched so far store
their  λ-variables  in  the  stack,  %3P%*.   References  to  those
variables in  the body of  the λ-expression are  made to  those
stack entries.  This scheme suffices  only for lambda or %3prog%* (local)
variables.   We have said that λ-expressions may refer to global
or free  variables.  The  lookup mechanism  simply finds the  current
binding of  that global in the  symbol table.  Notice that  this is a
different strategy than the global lookup of Algol.  In Algol, when a
procedure refers to a global we take the  binding which was current at
the  point of definition  of the procedure.   The  LISP mechanism is
called %2⊗→dynamic binding↔←%*.   It corresponds to physically  substituting
the body  of the definition  of the  function wherever it  is called.
Its model  of implementation is simpler than that required for Algol.
We don't need the ⊗→static chain↔← for this case of  global lookup.  Thus
interpreted expressions encounter  no problems when faced with global
variables.  There are potential  difficulties for compiled code.   If
all we store  of the stack in a  compiled function is the value  of a
variable  then another  program which  expects  to use  that variable
globally will have no way of  finding that stored value.  One  scheme
is to store  pairs on the stack:  name and value (LISP#1.85) then we
can  search the stack for  the latest binding.  It  works.  With this
scheme we  can dispense  with the  ⊗→%3VALUE%*-cell↔←.  Actually this  scheme
isn't  all that bad.   The  compiler can still  `know' where  all the
local variables  are on  the stack  and  can be  a bit  clever  about
searching for  the  globals.   Notice this  is the  old symbol  table
mechanism  (⊗→a-list↔←)  again.   LISP#1.85 was  designed  for  a paging
machine (XDS#940) and a  few unpleasant features crept in because  of
this.   (However, on  the positive  side some  nice coding  tricks to
minimize page references also arose.)

The solution proposed  by the LISP 1.6  implementation called
%2⊗→shallow  binding↔←%*, allows  the compiled  code  to directly  access the
%3VALUE%*-cell in the symbol table.  There is an artifact in the compiler
(and  assembler) called  %3SPECIAL%*.    Variables which  are  to be  used
globally  are declared ⊗→special variables↔←.   When a  variable, say %3x%*, is
declared special the compiler will emit a reference to %3x%* as 
%3(MOVE#AC%4i%*#(SPECIAL#X))%1
or %3(MOVEM#AC%4i%*#(SPECIAL#X))%1 rather than the corresponding
reference to a location on the  stack.  When the LISP assembler  sees
the indicator %3SPECIAL%*, it will search the  symbol table for the %3VALUE%*-cell
 of %3X%* and  assemble a reference to that cell.  Since the location
of the value  cell does %2not%*  change, we can  always find the  current
binding posted  in the  %3cdr%*-part of  that cell.  Notice too  that any
interpreted function  can also sample the %3VALUE%*-cell so global values
can be passed between compiled and interpreted functions.  The values
of local variables are still posted on the stack.
This then is the reason for depressing the actual value one level.

****pic
.GROUP SKIP 6;

We have not yet  discussed the mechanism which will  allow us
to  pass back and  forth between compiled  and interpreted functions.
To complete that discussion we must introduce the %aSM%* instruction for
calling a function:

.BEGIN TABIT1(19);TURN OFF"←";

PUSHJ P fn\%3C%*(P) ← %aPC%*
\P ← %3C%*(P) + 1
\%aPC%* ← fn. This is called the "push-jump" instruction. Exit with POPJ.
.END

First we 
require that the  calling conventions for both kinds  of functions be
isomorphic.

When an interpreted function calls  a compiled (or primitive)
function, %3eval%* will  look for the indicator,  %3SUBR%*; then retrieve the
machine address of the code and enter via a %3PUSHJ%*. That code should exit
(back to %3eval%*) via a %3POPJ%*, after assuring that the stack, P, has
been restored to the state at the time of entry.

Compiled functions  call other functions  via the %3(CALL#%1n%*#(E#%1fn%3))%1
artifact.  The %3CALL%*  opcode is actually  an illegal instruction
which is trapped to a submonitor inside %3eval%*.  This  submonitor looks
down the  property list  of the  atom, fn,  for a  function indicator
(%3SUBR, EXPR%*,  etc).  The  function is  called  and  control  is then
returned to  the address  immediately following  the %3CALL%*.   In  many
cases this %3CALL%* can be replaced  by a %3(PUSHJ#P#%1fn%3)%*, but not always as
we will see next.
.END
.SS(Functional Arguments,,P3:)

***more h.s.***

***farting with funarg***

funarg b-w. and weizen

**add deep-binding compiler**

what does this say about  the CALL mechanism in the compiler?  It says that
the calling  mechanism  for  a  functional argument  must  always  be
trapped the submonitor and decoded.  We cannot replace that call with
a  PUSHJ to some machine  language code for  the function because the
function referred to can change.  We actually use  a CALLF instruction
to designate a call on a functional argument.
	
.SS(Tracing and debugging in LISP)

When can the  %3CALL%* instruction be  replaced by a %3PUSHJ%*?   The
%3PUSHJ%*  instruction  is  used to  call  a  machine language  function.
Obviously  if  we  are  calling  an  interpreted  function, (it  has
indicator %3EXPR%*  of %3FEXPR%*) %3PUSHJ%*  is the wrong thing  to do.   In this
case  we must pass  control to  %3eval%*, evaluate the  function with the
appropriate arguments,   return the value  in %3AC1%* and finally  return
control to the instruction following the %3CALL%*.  If the function being
called is a  machine language  routine (indicator is  %3SUBR%* or  %3FSUBR%*)
then  we  could  replace   the  %3CALL%*  with  a  %3PUSHJ%*.  This  would
`short-circuit'  the call on  the submonitor  and the calling  of the
function could be  done more quickly.   There  are many occasions  in
which we do not wish to make this replacement, however.

Assume for  the  moment that  I am  mortal and  that my  LISP
program  has some  bugs.   Crucial  pieces of  information  about the
behavior of the program are: which functions are being  entered, what
are  the actual  parameters, and what are the  values being returned.
Assume that  we wish to monitor the behavior of the function, %3FOO%*. We
will hide the  real definition of %3FOO%*  on another symbol table  entry
(using %3gensym[]%*)  and redefine %3FOO%* such  that, when it  is called, it
will:

.BEGIN narrow 10;;

%21.%*  print the values of the current actual parameters.

%22.%*	use %3apply%* to call the real defintion of %3FOO%* with the current parameters.

%23.%*	print the value of the call on %3FOO%*.

%24.%*	return control to the calling program.
.END
This device is called tracing.

Since  %3FOO%*  may  be  recursive  we   should  also  give  some
indication of the  depth of recursion being executed.  Now every call
on %3FOO%* will give us  the pertinent statistics.  Interpreted calls  on
%3FOO%* will  go through %3eval%*, and  if %3(CALL ... FOO)%* is being  used in the
compiled  code  the  submonitor  can  pass  control  to  the  tracing
mechanism; but if the %3CALL%* is replaced by a %3PUSHJ%*, the control passes
directly to the machine language code for %3FOO%* and we cannot intercept
the call.

On most implementations  of LISP the %3PUSHJ-CALL%*  mechanism is
under  the  control   of  the  programmer.    After  the  program  is
sufficiently debugged,  replace  the  %3CALL%*  with the  %3PUSHJ%*  and  the
programs will  execute faster.   But  be warned  that this  action is
irreversible on most machines; once the %3CALL%*s have been overwritten it's tough beans!!

A variant of this tracing scheme can  be used to monitor %3SET%*s
and  %3SETQ%*s in  interpreted %3prog%*s.   Since calls  on %3SET%* and  %3SETQ%* are
interpreted (by %3eval%*  and Co.),  we can modify  their definitions  to
print the  name of the  variable and the  new assignment, do  it, and
return.  (question: can you see why this perhaps won't (or shouldn't)
work for compiled code?)

This is a very brief description of debugging in LISP.  It again shows
some of the power resultant from having an evaluator  available at runtime.
Much more sophisticated debugging techniques
can  be implemented,  particularly  in an  on-line  implementation of
LISP. Perhaps the most comprehensive on-line LISP system is INTERLISP, an
outgrowth of BBN LISP. The details of this undertaking would take us too far
afield from our current discussion.
.SS(Macros and special forms,macros,P57:)
Recall our discussion of macros and ⊗→special forms↔← in {yonss(P18)}.
We wish  to extend our compiler to handle such definitions.

Consider the example of defining %3plus%* of an indefinite number of arguments
given on {yon(P58)}.
Notice first that difference in efficiency between the interpreted macro ({yon(P58)})
and the interpreted special form ({yon(P59)}) is very slight.  Both require calls on %3eval%*.
One requires explicit user calls on the evaluator; one does it
within the evaluator.
In the presence of a compiler we can frequently make execution of macros
more efficient than their special form counterpart. This is the case with %3plus%*.
When %3plus%* is called we know the number of arguments, and can simply
expand the macro to a nest of calls on %3*plus%*. For example:
.begin centerit;

%3
←plus[4;add1[2];4] %1expands to%* *plus[4;*plus[add1[2];4]] %1
which can be efficiently compiled. 
.end

.P73:
There is a closely related use of LISP macros which is worth mentioning.
Recall on {yon(P60)} we defined %3coef%* 
as %3car%*. Compiled calls on %3coef%* would invoke the function-calling
mechanism, whereas many compilers can substitute actual hardware instructions
for calls on %3car%*, resulting in more efficient run-time code.
So for efficiency's sake it would be better to write %3car%* instead of
%3coef%*. There are two objections to this. First, %3coef%* has more
mnemonic significance the %3car%*. Second, using %3car%* we have explicitly
tied our algorithm to the representation. Both are strong
objections.
Macros can help overcome both objections. Define:

←%3coef <%4m%*= λ[[l]cons[CAR;cdr[l]]]%1.

(Recall that the whole call %3(COEF ... )%* gets bound to %3l%*.)
So the user writes %3(COEF ...)%*; the evaluator sees %3(COEF ...)%* and
finally evaluates %3(CAR ...)%*; and the compiler sees %3(COEF ...)%*
and compiles code for %3(CAR ...)%*. So we can get the efficient code, the
readibility, and flexibility of representation with macros.

Since %3eval%* handles calls on special forms, we should examine the
extensions to %3compile%* to generate such code. We have seen that
in compiling  arguments to (normal) functions, we generate the code for
each, followed by code to save the result in the run-time stack, %3P%*.
The argument to a special form is %2unevaluated%*, by definition. All we
can thus do for a call of the form %3f[l]%*, where %3f%* is a special form,
is pass the argument, compiling something like:

.BEGIN CENTERIT;SELECT 3;GROUP;

←(MOVEI AC1 (QUOTE (l)))
←(CALL 1 (E F))
.END

This should also be clear from the structure of %3FEXPR%* calling in the %aSM%*
evaluator. 


←%2Problems%*

I. Extend the last %3compile%* function to handle macros.

II.  We have seen the (necessarily) inefficient code generated by a compiler
for %3FEXPR%* calls.  Assume ⊗→%3and%*↔← is a special form with an indefinite
number of arguments.  Show how to modify %3compile%* to recognize %3and%*
and compile efficient code for its execution.

.SS(Numbers,numbers)

In most implementations of LISP, numbers are stored  as very simple kinds of
atoms:  they do not  need print names,  but since  we should probably
allow fixed and floating point representation, we do  need indicators
for these properties.  Thus:

.BEGIN TABIT2(10,45);GROUP;
\fixed-point 1\floating-point 1.0
\|\|
\|--→%7α~~]%1--→%7[%bFIXNUM%7]~~]%1--→%7[~%11%*~]\%1|--→%7α~~]%1--→%7[%bFLONUM%7]~~]%1--→%7[%1201400000000%7]

.END
Notice that each actual number is stored in FWS.  This representation
is a  bit expensive.  On  some machines we can use  a coding trick to
improve representation of some  numbers.  Assume that the  addressing
space of the machine  is 2%818%* and that the usual  size of a LISP
core image is significantly smaller, say, N.  Then all memory address
references greater than N  are illegal (and trapped by  the monitor).
What we  will do is use  these illegal addresses to encode  some of the
smaller positive and  negative integers, mapping  zero on the  middle
address, the  positive numbers to  lower addresses and  the negatives
onto  the  higher   addresses.    Thus  these  smaller  integers  are
represented by pointers outside of the normal LISP  addressing space.
This  trick can  considerably decrease  the storage  requirements for
jobs  heavily using small  numbers.  (Numbers are  not usually stored
uniquely).




.group
.GROUP SKIP 20
%2←Picture of INUM Space%*
.apart



Most  numerically oriented  programs  are  faced  at some  time  with
overflow.  That is, they attempt  to construct a number  which is too
large to  be represented  in one  machine location.    There are  now
several   versions   of   LISP  which   will   automatically   change
representation  when faced  with overflow.   This  new representation
called Bignums, could have the following structure:


.group
.group skip 7;
←%2Structure of a BIGNUM%*
.apart



The value of Bignum is given by:

 
where α-1 is  the largest number  representable in one  machine word.
The intertranslations  between Inums, Fixnums or Flonums, and Bignums
is done automatically by %3eval%* and Co.
.SEC(Storage structures and efficiency)

Though it is true that any algorithm can be coded in terms of
manipulations of binary trees, there are many instances in which more
efficient organizations of data exist.

At the most elementary  level are vectors and arrays.   These
data structures could  certainly be stored in a list structure format
and individual components accessed via %3car-cdr%* chains.  However, most
machines  have a  hardware  organization which  can  be exploited  to
increase   accessing   efficiency  over   the   list  representation.
Similarly, strings can  be represented as  lists of characters.   The
string processing operations are expressible as LISP algorithms.  But
again this is usually not the most resonable representation. Even  at
the level of list-structure operations, simple binary trees might not
be the most  expeditious representation for every problem.  Also many
of the algorithms we  have presented in  LISP are overly wasteful  of
computation time.  This section of notes will begin an examination of
alternatives   to  LISP  organization.     There  is   no  best  data
representation, or no best algorithm.  The representations you choose
must match your machine and  the problem domain you are studying.  If
your application is strictly numerical then list-structure is not the
answer; if you wish to manipulate simple linear strings of characters
then list processing is too general.  And there are many applications
of list processing which are sufficiently well-behaved that you don't
need a storage  allocation device as complex as  a garbage collector.
The point  is that if you have seen the list-processing techniques in
a rich environment  such as  LISP and have  seen the applications  to
which  LISP may  be put,  then you  will be  prepared to  apply these
techniques  in  a  meaningful  way.    Many  times  an  (inefficient)
representation in  LISP  is all  that is  needed.   You  get a  clean
representation  with comprehensible algorithms.   Once you've studied
the algorithms, efficiencies might come to mind. At that  time either
recode the problem using some  of the obscene LISP programming tricks
or drop into machine language if very fine control is required.  Once
you have  %2a%*  representation it  is  easy to  get  better ones.    For
example,  once you have  a compiler  which is   correct  it is
easier to describe a smarter one.
		
This section will describe other representations than LISP binary trees
and will show some ways of increasing the efficiency of LISP programs

.SS(Bit-tables)
Bit tables: In the marking phase of a garbage collector it is
necessary to  record the marking of each word.   On many machines the
marking of a word is signified by setting a bit in a bit table or bit
map.  For example:




.GROUP
.GROUP SKIP 8;
←%2Bit map for garbage collector%*
.apart




This  might be  done for  several  reasons.   The  natural choice  of
setting  a mark-  bit  in the  actual word  being  marked may  not be
possible or not the best strategy: 
.BEGIN INDENT 0,6;
1.  for words in  FS, there is  no
room if each  word contains exactly two addresses; or  

2. the word is
in  FWS and  the  meaning of  the information  stored there  would be
changed;  

3. also  the  garbage  collector must  initialize  all  the
mark-bits to  zero before the actual marking  process begins (look at
the g.c. algorithm).  It is faster  on most machines to zero a  whole
table rather than zero single bits in  separate words; and finally 

4. in  garbage collectors for more  complicated data structures, marking
with a bit table becomes a necessity.

.END
.SS(Vectors and arrays)
.BEGIN TABIT2 (10,40);CENTERIT;FILL;
%2Vectors%*:  Vectors (or  one  dimensional arrays)  are  usually
stored sequentially in memory.  Simple vectors are usually stored one
element to a  memory location though  this is not  a necessity.   For
example a complex vector is very  naturally stored as pairs of cells;
or if  perhaps you would allow vectors of non-homogeneous data modes,
each element would  have to include type  information.  In any  case,
most languages make some restrictions on the behavior of vectors such
that efficient accessing of elements can be made.  There is a natural
simulation of  a stack as  a (sequential) vector  with access  to the
stack made via a global pointer to the vector.

%2Arrays%*: Arrays are multi-dimensional data  structures.  Since
most  machine memories are linear  devices we must map  arrays onto a
linear representation.   We will  restrict attention fo  the case  of
two-dimensional  arrays.   Most  of the  discussion generalizes  very
naturally.   A very common device is to store the array by rows; that
is,  each  row is stored sequentially,  first, row 1; then  row 2,...
Given this representation there  is a trivial calculation to find the
location of an arbitrary element, A[i;j], if we know the location  of
the first  element, A[1;1] and  the extent of  the dimensions  of the
array.  For an array A[1:M; 1:N]

←loc[A[i;j]] = loc [a[1;1]] + (i-1)*N + (j-1)

In languages like Fortran which require that the size of the array be
known at compile-time  the compiler can generate the accessing code
without problem.  Languages, like Algol 60, and some versions of LISP
which allow the size of an  array to be determined at runtime require
a bit more care.  Algol 60, for example requires that you declare the
type (real, boolean,  etc.) of  the array and  specify the number  of
dimensions  in the  array,  but you  can postpone  until  runtime the
designation of the size of each dimension.  To handle this complexity
a dope vector is  introduced. The compiler can determine  the size of
the dope vector, but  not the contents.  The dope vector is filled in
at runtime and  contains information about the  actual extent of  the
array bounds.   Also since  the size of the  array is not  known, the
compiler  cannot   allocate  space  for  the  array  elements.    The
allocation must be  done at runtime.   When the array declaration  is
executed we must  know all the information about the  array.  At that
time we add the  array-bound information to the  dope vector and  add
information telling where  to find the  array elements.   Assume that
the  array elements are stored  by rows.  Look  at the calculation of
the location of element, A[i;j].   For specific execution ofan  array
declaration much  of this information  is constatnt; the  location of
the array  elements, in particular, A[1;1] and the number of columns,
N, is fixed.  Thus we rewrite the calculation as:

\constant part\variable part

\ [loc [A[1;1]]-N-1]       +\  	(i*N+j)

The constant  part is stored  in the  dope vector.   When we wish  to
reference  an element A[i;j] we  need only compute  the variable part
and add it to the constant part.

The dope vector for A [1:M; 1:N] perhaps might contain
.GROUP SKIP 10;




There is another scheme  for storing arrays which is  used in
some of  the Burroughs machines. Each row  is stored sequentially and
access  to  separate  rows  is   made  through  a  device  called   a
`mother-vector'.   The mother vector is  a vector of pointers  to the
rows.  Thus:




.GROUP SKIP 10;





Notice that the accessing computation is very  cheap.  Another effect
is  that all rows  need not  be in memory  at once.   On a  paging or
segmenting machine (we  will talk  about machine organization  later)
this array organization can be helpful.  If an access to a row not in
core  is made, a `page  fault' is raised; the  monitor brings the row
into memory and the computation continues.   The mother-vector scheme
generalizes  nicely  to   multidimensionality  and  can  be  used  in
conjunction with a dope vector.

.END
A typical implementation on an array facility in LISP would include
a declaration:

.BEGIN INDENT 0,10;
⊗→%3array%*↔←%3[%1<identifier>;<type>;<bounds>; ... <bounds>], where the
identifier names the array; the type could be numeric or sexpr; and  finally
a declaration of upper and lower bounds for each dimension would be needed.
%3array%* is a special form whose effect is to make the array name a %3SUBR%*,
whose code is the calculation of the dope vector. Thus:
.END
.GROUP SKIP 15;
.BEGIN INDENT 10,10;
If we are to store sexprs in the array then the ⊗→garbage collector↔← must
be able to mark the entries. This is the reason for including type information.

When an array element is to be referenced, then the subscripts are evaluated
(recall that the array name was declared as a %3SUBR%*) and the dope vector code
is executed, resulting in a reference to the appropriate cell.
.END

We also must be able to store information in the array.
.BEGIN INDENT 0,10;
%3store[%1<name>[<subscr>; ... <subscr>];<value>] : ⊗→%3store%*↔← is a special form
whose effect is to store the value of <value> in the designated array element.
.END
.SS(strings and linear LISP,string processor,P27:)
.BEGIN TURN ON "←";
Strings and string processors are an important class
of data  structures and algorithms.  Powerful  string processing is a
necessity  for any  well  developed  compiler-writing  system.    The
organization  and  implementation  of   a  general  string  processor
directly parallels LISP.  In fact a subset of LISP,
⊗→linear LISP↔←,  is a nice notation for string algorithms.

A string is a sequence of characters.   A reasonable language
(not PL/1) for string processing should allow the creation of strings
of arbitrary length at runtime; it should allow the generation of new
strings and the  decomposition of existing  strings.  If  strings of
arbitrary length are  to be created, an organization similar to FS in
LISP can be used with, perhaps, a string garbage collector.   We will
assume this most general case.
The machine memory will  contain at least a ⊗→string  space↔←, an
evaluator, a symbol table, and a garbage collector.

String space is a linear sequence of cells, each of which can
contain exactly  one charcter.   A string  will be  represented as  a
sequence of sequential character cells.  A string variable will be an
entry in  the symbol table; the current value of the variable will be
represented as a pair; character count and a pointer to the beginning
of the character sequence.

Thus:

.GROUP SKIP 4;

.BEGIN TURN OFF"←";
We must make some decisions about how  we manipulate strings: when we
perform %3x ← y%*, do we copy the symbol table pair of %3y%* into that of %3x%*, or
do we make a new string isomorphic to %3y%* and point %3x%* at it.   It makes
a  difference.    We  will   choose  the  former,  copying  only  the
`descriptor',  that  is,  we  will  share  strings  (and  substrings)
wherever possible. This decision makes the  storage requirements less
expensive, but will make our  life more difficult when we worry about
⊗→garbage collection↔←.   There are  three  primitive functions: ⊗→%3first%*↔←,
⊗→%3rest%*↔←,  ⊗→%3concat%*↔←  (read: %3car%*,  %3cdr%*,   %*cons%*).
.END

.BEGIN INDENT 0,10;
%3first[x]%*  is  the first
character of the string represented by %3x%*.  %3first%* is undefined for the
empty string. For example:
.END

←%3first[ABC]%1 is %3A; first[%1∧%3]%* is undefined.

%3rest[x]%* is  the string  of characters  which remains  when the  first
character of  the string is deleted.  %3rest%* is also undefined for the
empty string. For example:

←%3rest[ABC]%* is %3BC%*

.BEGIN INDENT 0,10;
%3concat[x;y]%* is a function of two arguments.   %3x%* is a character; %3y%* is
a  string. %3concat%* forms  a string  consisting of the  concatenation a
copy of %3x%* and a copy of the string, %3y%*.  For example:
.END

←%3concat[A;BC]%* is %3ABC%*
	
There are three string predicates:

.BEGIN CENTERIT;
←⊗→%3char%*↔←%3[x]%1:  is %3x%* a single character?
←⊗→%3null%*↔←%3[x]%1:  is %3x%* the empty string?
←%3x ⊗→%3=%*↔← y%1:  are %3x%* and %3y%* the same character?

For example:

←%3char[A] %1is true
←%3char[AB] %1is false
←%3AB = AB %1is undefined
.END

	Now to implementations:
%3first%* generates a character  count of 1 and a  pointer to the
first character of the parent string.
%3rest%* generates a character count of one less than that of the
parent and a pointer to the second character of the parent string.

%3concat%* is a  bit more  problematic.   We copy %3x%*  and copy  %3y%*,
generate  a character  count of  the sum  of those  of %3x%*  and %3y%*,  and
generate a pointer to the character of the copy of %3x%*.  The copies are
made in the free string space pointed to by the %2⊗→string space pointer↔←%*.
The obvious  question of  what to do  when string space  is exhausted
will be postponed  for a moment.   The implementations  of the  three
predicates are easy: we will blur  the distinction between characters
and strings  of length 1.  Thus %3char%*  need check the character count.
%3null%* says character count is 0.  What about = ?  Obviously characters
are  not  stored   uniquely,  so  we must  make  an  actual character
comparison.

Now  ⊗→garbage collection↔←.    In  some  ways a  string  garbage
collector is simpler and in some ways more difficult than a collector
of list-structure.   The  marking phase  is much  simpler: using  the
descriptor in the symbol table, mark  the character string.  Since we
are sharing  substrings, we cannot stop the marking simply because we
have encountered a previously  marked character. 
But at least  the marking is not recursive.   However, the collection
phase needs to be  more sophisticated for  string processors.   Since
strings are  stored linearly (or  sequentially), a  fragmented string
space  list  is  of  little  use.    Thus  we  must compact  all  the
referenceable strings into one end of string space, freeing  a linear
block for the new free string space.  Since we are sharing substrings
a  little care  needs  to  be exercised.    When  we move  a  string,
obviously the descriptor of any variable referencing any part of that
parent string must be changed to reflect the new location.  So before
we begin the relocation of strings  we sort the string descriptors on
the  basis of their  pointers into  string space.   We then recognize
each parent string, moving it down into freed  locations and updating
the address  pointers of any  substrings.  We  continue this process.
Eventually all strings will  be compacted down  in string space.  The
free space  pointer will  be set  and the  computation can  continue.
Compacting garbage collectors  can be adapted for use in LISP or more
general types of data structures.

.END
.SS(%3rplaca%* and %3rplacd%*)

.BEGIN TURN ON "←";
We  will  first look  at  some LISP  coding
tricks which when used judiciously, can increase efficiency, but when
used in a cavalier manner can result in mystery.  First, LISP does an
awful lot of copying.  Consider:

%3←append <= λ[[x;y][null[x] → y;T → cons[car[x];append[cdr[x];y]]]]%*

This function copies %3x%* onto the front of %3y%*. Note: %3y%* is not copied.
Or recall the %3subst%* function: it generates  a copy with the correct
substitutions made.   The copying is necessary  in general. It  keeps
unsavory side effects from happening.

Let's look at %3append[(A B C);(D E F)]%*.  It appears that we
could get the appropriate effect of %3append%* by %3cdr%*-ing down the list
%3(A B C)%* until we found the terminator, then replace it with a pointer
to the list %3(D E F)%*.  Thus:


.GROUP SKIP 6;

What's wrong here?  Consider the sequence of statements:

.BEGIN TABIT1(30);TURN OFF"←";SELECT 3;

\i ← (A,B,C)

\j ← (D,E,F)

\k ← append[i;j]
.END

Then if %3append%* worked  as advertised above, (changing the  %3cdr%* of the
last element of %3i%*) the following evil would be perpetrated: the value
of  %3i%*  would be  changed  surreptitiously!!  %3i%*  now  has   the  value
%3(A,B,C,D,E,F)%*.   Language features which  do this  are evil.   It is,
however,  quite useful to be  evil sometimes.   Notice that any value
which was sharing  part of the structure  of %3i%* will also  be changed.
This can cause real mystery!! Well the world is good, and %3append%* does
not work as above.   The LISP  function which %2does%*  work this way  is
called %3nconc%*.   It  can be  defined in  terms of  a primitive  obscene
function, %3rplacd%*.  There are two primitive obscene functions:

⊗→%3rplaca%*↔←%3[x;y]%* replace the %3car%*-part of %3x%* with %3y%*.


.GROUP SKIP 6;




⊗→%3rplacd%*↔←%3[x;y]%* replace the %3cdr%*-part of %3x%* with %3y%*.



.GROUP SKIP 6;




Thus %3nconc%* can be defined as:
.BEGIN SELECT 3;TABIT1(20);TURN OFF"←";

nconc <= λ[[x;y]prog\[[z]
\ [null[x] → return[y]];
\ z ← x;
\a[null[cdr[z]] → rplacd[z;y];return [x]];
\ z ←cdr [z];
\ go[a] ]]

.END
These functions  must be  used with  extreme caution.   They are  not
recommended for amateur hacking.  They are introduced here simply to
show that  it  is  possible to  improve  on the  efficiency  of  pure
algorithms by resorting to these coding tricks.
Consider:

.BEGIN SELECT 3;TABIT1(30);TURN OFF"←";

\x ← (NOTHING CAN GO WRONG);
\rplacd[cdddr[x];cddr[x]];
\print[x];

.END

So we can use %3rplacd%* to generate circular lists (and to generate wall
paper  by printing  them!!).
Circular lists cannot be generated in LISP without functions like
%3rplaca%* and %3rplacd%*.
See the problem on {yon(P55)}.
In  general,  to circularize  a non-empty
list, %3x%*, %3rplacd[last[x];x]%* suffices where:

←%3last <=λ[[x][null[cdr[x]] → x; T → last[cdr[x]]]]%*

←%2Problems%*

%21.%1  What is the effect of evaluating %3rplacd[x;cdr[x]]%*?
.END


.SS(Applications of %3rplaca%* and %3rplacd%*)
We begin with rather simple examples. Consider the  problem of inserting
an element into the middle of a list.  For example let %3x%* be the list,
%3(A B C)%*.  If we wished to insert an atom, say %3D%*, between %3B%*
and %3C%*, we could perform:

.BEGIN CENTER; SELECT 3;turn off"←";
x ← cons[car[x];cons[cadr[x];cons[D;cddr[x]]]].
.END

Indeed, in general, we have little choice but to recopy the the initial segment
of %3x%*, adding %3D%* into the appropriate place.  A similar technique is
obviously available to delete a specified element from the interior of a list.

Careful use of %3rplacd%* can, in some instances, replace the heavy use of %3cons%*.
%3cons%* always carries with it the threat of a call on the garbage collector.

For example, given the list %3(A B C)%* with pointers, %3x%* and %3y%*, into it
as follows,

.GROUP SKIP 5;

we could insert the element, %3D%*, %2after%* the first element in %3y%* by:

←%3rplacd[y;cons[D;cdr[y]]%*, giving:

.GROUP SKIP 5;

(Notice that %2one%* %3cons%* is unavoidable.)

But as always, be warned that the value of %3x%* has also been changed; and
any sexpr sharing the list %3x%* or %3y%* as a sublist has also been affected.

We can also use %3rplacd%* to delete not the %2first%*, but the next element,
in %3y%* by:

←%3rplacd[y;cddr[y]].%*

Similarly, we can use %3rplaca%* to modify an element in a list (or sexpr).
To change the first element in the list, %3y%*, to the sexpr, %3z%* use

←%3rplaca[y;z]%*.

Notice that the uses of %3rplacd%* for insertion and deletion are couched in terms
of insert %2after%* and delete %2after%*, rather than insert %2at%* or delete %2at%*.
If you look at a diagram you will see why:

.GROUP SKIP 7;


To delete the element %3B%* requires modifying the %3cdr%*-part of the predecessor
cell.  Similarly to insert at a specified cell. How could we write such modifying
functions?  A simple, perhaps inefficient scheme, would be to start another pointer
 from the beginning of the list, looking for the cell whose %3cdr%* pointed to the
desired spot; then make the modification.  

If these `modification-%2at%*' functions were to be performed very frequently
then it might be worth starting %2two%* pointers down the list, one at %3x%*,
one say %3y%* at %3cdr[x]%*, as above.  Then %2testing%* could be done using %3y%*
and the %2modification%* could be done using %3x%*. When we move %3y%* to
%3cdr[y]%* we move %3x%* to %3cdr[x]%*.  What happens if we wanted to modify
%2before%* rather that %2at%*? We could proliferate the `back pointers', but
perhaps if this kind of generality is required a change of representation
is called for. More complicated data representations are discussed
in detail in ⊗→Knuth's Kompendium↔←,Khapter 2.


The LISP system uses %3rplaca%* and %3rplacd%* heavily; for example, functions
which modify properties on the p-lists use these functions. Here are
two p-list manipulating functions, ⊗→%3putprop%*↔← and ⊗→%3remprop%*↔←.

.BEGIN INDENT 0,10;

%3putprop%* is a function of three arguments, %3n%*, an atom; %3i%*, an indicator;
and %3v%* a value. The effect of %3putprop%* is to attach the indicator-value pair
to %3n%*.  If the indicator is already present then we will simply change its value
to %3v%*; if the indicator is not present then we will add the indicator-value 
pair to the front of the p-list.  Since %3VALUE%*-cells have a slightly different
format (see {yon(P50)}), there is special glitch for adding or modifying them.
.END

.BEGIN SELECT 3;TABIT2(5,8);GROUP; TURN OFF"←";

putprop <= λ[[n;i;v] 
   prog[[m]
\\m ← cdr[n];
\a\[eq[car[m];i] → go[b]]
\\m ← cddr[m];
\\[m → go[a]];
\\[eq[i;VALUE] → rplacd[n;cons[VALUE;cons[cons[NIL;v];cdr[n]]]];return[v];
\\ T → rplacd[n;cons[i;cons[v;cdr[n]]]];return[v]  ]
\b\[eq[i;VALUE] → rplacd[cadr[m];v];return[v];
\\ T → rplaca[cdr[m];v];return[v]] ]]

.END
Notes:

1. %3[m → go[a]]%* is a trick you have seen before.

2. Extended conditional expressions are used here.

%3remprop%* is simpler.

.BEGIN INDENT 0,10;
%3remprop%* is a predicate, whose importance lies in its side effects. %3remprop%*
has two arguments, %3n%*, an atom, and %3i%*, an indicator. If the indicator is found on the
p-list of the atom, then %3remprop%* removes the indicator-value pair and returns
%3T%*, otherwise %3remprop%* does nothing and returns %3NIL%*.
.END

.BEGIN SELECT 3;TABIT2(5,8);GROUP;TURN OFF"←";

remprop <= λ[[n;i]
   prog[[m]
\\m ← n;
\a\[eq[cadr[m;i] → rplacd[m;cddr[m]];return[T]]
\\m ← cddr[m];
\\[m → go[a]]
\\return[NIL] ]]

.END

Applications of %3rplacd%* will occur inside ⊗→%3ratom%*↔← and
inside the ⊗→garbage collector↔←.  For example the ⊗→sweep phase↔← might
be  described as:

.BEGIN SELECT 3; GROUP;TURN OFF"←"; TABIT2(22,25);

sweep <= λ[[x;y]prog\[[z]
\\z ← NIL;
\a\[nap[x] → z ← rplacd[x;z]]
\\x ← down[x];
\\[eq[x;y] → return[z]]
\\go[a] ]]

.END

Where %3sweep%* is to sweep from %3x%* to %3y%*.  %3nap%* is a predicate
returning %3T%* just in the case that its argument is still marked `not available';
and %3down%* finds the `successor' of its argument in the linear ordering of the
memory cells.

As a final example we will describe a ⊗→fixup↔← mechanism (see {yonss(P7)}) using 
%3rplacd%*. Since our fixups will be  very simple when assembling compiled code, 
we will chain the forward references together via their %3cdr%*-parts. If an atom,
%3n%*, is defined to be a label it will have on its p-list, the indicator
%3SYM%* and a value representing the memory location assigned to %3n%*.
In the case of forward references to a label %3n%* two actions may occur.
Let loc be the memory location to be assigned to the instruction containing the
forward reference.
If this is the first occurrence of a forward reference to %3n%*, 
then the pair %3(UNDEF .(%* loc%3))%1 is added to the property list, and %30%*
is placed in the %3cdr%*-part of loc and the partial instruction is placed
in the %3car%*-part. Thus:

.GROUP SKIP 5;

Any succeeding references to %3n%*  result in changing the  %3cdr%* of the
p-list pair, call it v, to point to 
a cell whose %3car%*-part is  loc and whose %3cdr%*-part is v.  As above 
we deposit the partial instruction in the %3car%*-part and %30%* in the %3cdr%* part
of loc.  Thus the next reference would update our example to:

.GROUP SKIP 10;

When the label %3n%* finally is defined we must perform the fixups, 
delete the %3UNDEF%* pair, and add a pair %3(SYM%* . loc %3)%* on the p-list.

.GROUP SKIP 10;

Here are the functions. %3defloc%* is called when a label has been defined; 
 %3gval%* is called when a label is referenced.

.BEGIN SELECT 3;GROUP;TABIT2(25,32);TURN OFF "←";
defloc <= λ[[lab;loc]prog\[[z]
\\[z ← get[lab;UNDEF] → go[fixup]
\a\return[putprop[lab;loc;SYM]]
\fixup\[null[z] → rplacd[lab;cdddr[lab]];go[a]]
\\deposit[car[z];plus[examine[car[z]];loc]]
\\z ← cdr[z];
\\go[fixup] ]]
.END

.BEGIN SELECT 3;GROUP;TABIT1(15);
gval <= λ[[lab]\[get[lab;SYM];
\ T → putprop[lab;cons[loc;get[sym;UNDEF]];UNDEF]0]]
.END

Notes: %3gval%* is full of pitfalls.

%21%*.  %3loc%* is a global variable.

%22%*.  There is no e%41%*; we assume that if p%41%* evaluates to something not
equal to %3NIL%*, then that value is the value of the conditional expression.

%23%*.  Otherwise  the %3putprop%* is executed and %30%* is returned.

See problem III, {yon(P10)}, and problem *** at the end of this section for 
the description of a complete assembler for our latest %3compile%*.

←%2Problems%*

assembler

II. More on %3ratom%*.

Recall the discussion of %3ratom%* in {yonss(P13)} and {yonss(P14)}.
Now that you know about %3rplaca%* and %3rplacd%* write a more detailed
version of %3ratom%*.

III. Recall the function which reverses the top-level elements of a list.
On {yon(P16)} and {yon(P23)}
we wrote it in various styles and with varying degrees of efficiency.
All of these functions used %3cons%*; however it is clear that we should be
able to reverse a list without using %2any%* new cells.
Write an AMBIT algorithm  for such a reversing function. Express this
algorithm as a LISP function. If you use %3prog%* don't use any %3prog%*-variables.

.SEC(Systems Organization)

There are  many applications of  data structures  which arise
very  naturally in the domain  of systems programming.   This section
will begin  with  a  very  brief historical  description  of  systems
organization, from the bare machine to multi-processing.
	In  the  early  days of  computers,  operating  systems  were
non-existent.   You would  sign up for  a couple of  hours of machine
time, appear  with your  card deck  or paper  tape,  and operate  the
machine.  Debugging devices consisted of a sharp pointed stick, and a
quick  hand on the console  switches.  This  means of programming was
very satifying to  many of the  programmers, but machine  utilization
left something  to be desired.   Much of  the time the  machine would
sitt idle (stopped) as  you would think  about what to  do next.   As
processing speed and  machine costs increased it became  evident that
this  mode  of operation  had to  go.   The  first  operating systems
consisted of a dull  slow object called  an operator and a  satellite
computer on which an input tape  consisting of many separate jobs was
created.   Each  job  on the  input tape  was swquentially  read into
memory, executed and the output presented to an output tape.  If some
abnormal  behavior  was  detected  in  your program,  you  were  also
presented with an  often uninspiring  octal dump of  the contents  of
memory. Whenever a job required say, a  data tape, the operator would
be notified,  and the machine would wait  until the tape was located,
mounted, and readied.  There was a moderately small  resident monitor
which controlled  the input, output  and perhaps the timing  of jobs.
Gross  utilization of the machine was  increased, however at the cost
of  easy  debugging.    This  mode  of  operation   is  called  batch
processing.

The CPU  (central processing  unit) still  locks up when  I/O
devices  aren't ready and the  user can physically  halt the machine.
For this  model and  most  of the  future discussion,  it  simplifies
matters to  assume that the  monitor resides  in a separate  core box
from that which contains user programs.

Thus:

.GROUP SKIP 10;







The  user programs  are  loaded  into  explicit (hard)  locations  in
memory,  and it is  assumed that  the user has  access to all  of the
addressing space of his core box.

In  an  attempt  to decrease  the  overhead  on  waiting  for
external actions (I/O  requests or operator intervention) we attach a
reasonably  fast  storage  device  (and  increase  the  size  of  the
monitor).  This storage device is  capable of holding many user jobs.
Whenever  a user (loser)  program requires a service  which cannot be
satisfied immediately,  the  monitor will  swap  the program  out  of
memory onto  this storage device, initiate action  which will tend to
satisfy the request, and bring  another job into core, beginning  its
execution.   This new job  may either  be the next  job on the  input
stream, or  a job which was swapped out and  now is ready to run. The
user still is given  the whole addressing  space, he is still  loaded
into  explicit memory  locations, but  the monitor  must now  be more
cleaver.   It must  be able  to recognize (or  `trap') requests which
would lock up the CPU.  It must be able to make decisions as to which
job to run next.





.GROUP SKIP 10;





Clearly  there  are   grossinefficiencies  in  the   present  scheme.
Allowing, or in  fact requiring, that each user have access to all of
memory is too generous.  Assume that our memory size is 32→ words and
assume that we  have 16K jobs which  are ready to run.   We should be
able  to load one job  into locations 0 - (16K-1)  and load the other
job into the  other half of memory.   When one job  requires external
service, we  should be able to  switch the CPU to  begin execution of
the other job provided that we save all information about the current
state of the suspended jog.  The point is  that it takes time to swap
jobs in and out  of core so thaat anything we can do to decrease this
overhead is  a winner.   What  are the  added  requirements for  this
scheme?  Manily we must have some  scheme for keeping the jobs out of
each  other's hair.  This  is usually done by  a hardware addition to
the machine  called the protection  register.
In this simple scheme the protection register  would be loaded by the
monitor  with the  upper  and lower  bounds on  the  addressing space
accessible to the current job.  Then every memory reference made by a
program is filtered  through the protection register.   Obviously the
instruction  to  load  protection register  should  be  restricted to
execution by the monitor.

What are  the inefficiencies in  this scheme?   Consider what
happens  when  we have  to  swap a  job  out of  memory.    Since the
addresses  used  by  the  program  are  explicitly  tied   to  memory
locations, we must swap that job  back into exacly the same locations
if  it is  to run correctly.   Consider  two 16K  programs whose only
effect is to execute `jump-self' loops ( L (JRST  L) ). Their initial
load might look like:


.GROUP SKIP 10;




If we swap out the top job and try to swap it back into the lower 16K
at some later time, we lose big.


.GROUP SKIP 10;





But clearly if the bottom  16K is available we should be  able to use
it.  We want to be able to swap our programs into any available block
of core which is of sufficient size.

To  accomplish  this we  add a  new piece  of hardware,  the
relocation register. Now our loader loads all our programs as if they
begin at location, 0.  Thus in the above example:


.GROUP SKIP 10;





To get the  appropriate effect when  we execute any program,  we bias
every  memory reference by  actual address assigned  to the program's
location 0.   This  bias is  put in  the relocation  register by  the
monitor before it begins execution of  the program.  With this scheme
we  can run any jobs in any block  of core which is the correct size.
All we  need do  is load  the  appropriate offset  in the  relocation
register.




.GROUP SKIP 10;



Now we can dispense with the two-core box approach.  Just use
one box and bias  every access in a user program by the length of the
monitor plus the usual offset:




.GROUP SKIP 10;




The actual harrdware can also be simplified now since the lower bound
on every user's addressing space is always zero.

Clearly, more refinements  need to be  made.  At  present the
only way  to interrupt a job is if he  terminates,  or calls for some
external action, or  attempts to perform  some illegal or  restricted
instruction.   Any operating system needs  to be able to  monitor the
amount of  CPU time spent on a job.  So we should have a programmable
clock  which can  be  set  by the  monitor  and  which will  send  an
interrupt to the at a  specified time.  Actually other hardware needs
to  be  added  to  our  entourage  if  we  intend  to  do  reasonable
time-sharing.  A  sophisticated   priority  interrupt  system   is  a
necessity.  Since  many of the applications of data structures appear
in time-sharing systems, we will say a bit about the behavior of such
systems.

.SS(Time-sharing organization)

What make  time-sharing viable  is the tremendous  difference
between human reaction time and machine speeds.  In a period of a few
seconds a well  designed t-s  system can satisfy  simple requests  by
many users.   If  a user must  wait a significant  length of  time to
obtain  a  response  to a  simple  command, then  your  system  is in
trouble.   The heart  of a  rapid  response is  a priority  interrupt
system.

A time-sharing monitor  must service terminals,  mass storage
devices and control the dynamic allocation of its memories.
Consider the  care and feeding  of a relatively  fast storage
device,  say  a  disk,  and  its  interaction  with the  sending  and
receiving of  characters from user  terminals. Most  disks require  a
sequence of  commands be  issued before an  actual data  transfer can
take  place.  Assume that there are two  commands: a seek to find the
appropriate area on the device, followed by the transfer command.  If
the CPU were tied up from the beginning of the seek to the end of the
transfer, significant  amounts of  CPU time  would be  lost.   If  we
issued the  seek, went  off to  do other  calculations, but were  not
responsive  enough when  the  seek was  completed we  might  miss the
chance to make the transfer due to intervening rotation of  the disk.
What we can do  is put the disk on a  high priority interrupt channel
and  the terminal keyboards on a medium  priority channel.  Issue the
seek, go back  to computation, perhaps  servicing the keyboards;  and
when the disk  is in position we will get  a high priority interrupt,
freezing the  state  of the  computation;  at this  time,  begin  the
transfer of information, dismissing the  interrupt and continuing the
computation.  Thus higher priority requests can interrupt lower ones;
any  lower priority  requests must  be suspended  or saved  until the
higher one is completed.  You might decide to design the  hardware to
allow recursive interrupts  on a particular channel  or might require
completion  before another  request can  be serviced.  

What about  the  data structures  used in  a complex  system.
Data structures  are used heavily in the  scheduling algorithms.  the
t-s monitor must make decisions about which jobs in the system are to
run.   These decisions are  based on such  simple things as:  the job
isn't  requesting service--dormant; the  job is waiting  for some I/O
device--I/O  wait; or  decisions  must  be based  on  more  difficult
criteria: the  job is ready to  run but is too big  for the currently
available allotment of core;  there is a job  ready which needs  fast
response or has been waiting inordinately long for service.

In  general a  vast  array  of  information can  be  used  in
deciding which  job to run next.   Usually these decisions take shape
by reqquiring that  the jobs currently in  the system be  partitioned
into  a  finite  set  of  waiting-lines  or  queues.  The  scheduling
algorithm manipulates  these queues as the status of the jobs change.
A queue  is  a  data structure.    Queues  are also  called  first-in
first-out lists (FIFO) or pop-up  lists.  In LISP parlance you append
new queue-elements to the end of  the list and take the elements  off
of the  front of  the  list.   It should  be obvious  where the  name
waiting-line comes from.

Queues are also used in the buffering schemes of I/O devices.
As we type `LOGIN.....'  to a t-s system, it is usually the case that
the character string first goes into a system buffer and when the CPU
is free,  the command is decoded.   Obviously we want  the monitor to
see  the character  string in the  same order  in which  we typed it.
That is the buffer is acting like a queue.

A queue can be implemented as simply a list with a pointer to
the front,  and a pointer to the end.   When you add something to the
end, you update one  pointer; wen you take  an element off the  front
you update  the other pointer.   There is  the obvious check  to make
sure  that you can recognize the empty  queue: when the front pointer
meets the end pointer:


.GROUP SKIP 6;


As with  stacks, the queue  is usually not  represented as a  list of
argitrary length.  A queue can be represented  as a sequential set of
memory locations, still with two pointers.  What happens when we have
filled the  last cell in  the sequence.  Well,   if some  process has
been removing items from the queue, then the front pointer has moved:


.GROUP SKIP 6;

In this case  the cells from  the first cell  in the sequence  to the
current position of  the front pointer are available.  Use `em.  That
is a queue is usually implemented as a sequential circular  list with
two pointers.   In this implementation the tests for  the empty queue
are  slightly more complex, but are still  obvious.  Notice too, that
we must now also test for the full queue.

In  system applications  it  is  usually  the case  that  one
process is filling the queue and one process is emptying it.  In this
application, a full  queue should simply put  the filling process  to
`sleep' (or suspend it), and when a queue becomes empty, the emptying
process  should  be  suspended.    There  are  some  interesting  and
non-trivial  problems   which   arise   in  connection   which   such
`cooperating processes'.

There are some interesting data  structure applications which
are connected with  the allocationa dn (?) liberation of storage. The
monitor  must  be  able  to   allocate  storage  to  jobs  as   their
requirements become known  and must also be able to  recover areas of
memory which  are no longer being used.  Similarly, since an integral
part of a large system is a file structure, the  monitor must be able
to handle  the demands of file  maintenance.  These  two problems are
related  but  solutions  for  core  allocation  are  not  necessarily
reasonable ones for file allocation.